<!DOCTYPE HTML>
<html lang="zh-CN">


<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
    <meta name="keywords" content="暑假LeetCode刷题集合（上）, 被动学习">
    <meta name="baidu-site-verification" content="fmlEuI34ir">
    <meta name="google-site-verification" content="yCy2azpds5XSuGZvis6OuA-XIGF5GuGpYRAaGfD6o48">
    <meta name="360-site-verification" content="b7c11a830ef90fd1464ad6206bb7b6e7">
    <meta name="description" content="最近决定巩固一下算法，开始刷leetcode每日一题，具体刷多久还不知道，刚开始是有点吃力，慢慢来。
【Day01】938.二叉搜索树的范围和题目：
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <title>暑假LeetCode刷题集合（上） | Shawlon`s Blog</title>
    <link rel="icon" type="image/jpeg" href="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/favicon.jpg">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/font-awesome.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">
    <style type="text/css">
        
    </style>

    <script src="/libs/jquery/jquery-2.2.0.min.js"></script>
    <script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>

    <script>
    var _hmt = _hmt || [];
    (function() {
    var hm = document.createElement("script");
    hm.src = "https://hm.baidu.com/hm.js?4d1d73af45a62734730491a6b6c41da4";
    var s = document.getElementsByTagName("script")[0]; 
    s.parentNode.insertBefore(hm, s);
    })();
   </script>


    <script>(function (i, s, o, g, r, a, m) {
        i['DaoVoiceObject'] = r;
        i[r] = i[r] ||
          function () {
            (i[r].q = i[r].q || []).push(arguments);
          };
        i[r].l = 1 * new Date();
        a = s.createElement(o);
        m = s.getElementsByTagName(o)[0];
        a.async = 1;
        a.src = g;
        a.charset = 'utf-8';
        m.parentNode.insertBefore(a, m);
      })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/0fcc9bf7.js", 'daovoice');
      daovoice('init', {
        app_id: "0fcc9bf7",
      });
      daovoice('update');
    </script>
  
  


    
        <script>
            (function(){
                var bp = document.createElement('script');
                var curProtocol = window.location.protocol.split(':')[0];
                if (curProtocol === 'https') {
                    bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
                }
                else {
                    bp.src = 'http://push.zhanzhang.baidu.com/push.js';
                }
                var s = document.getElementsByTagName("script")[0];
                s.parentNode.insertBefore(bp, s);
            })();
        </script>
    

    <script>
        (function(){
        var src = "https://jspassport.ssl.qhimg.com/11.0.1.js?d182b3f28525f2db83acfaaf6e696dba";
        document.write('<script src="' + src + '" id="sozz"><\/script>');
        })();
    </script>

    <meta name="baidu-site-verification" content="code-FwB5xSTmVO">




<style type="text/css" lang="css">
    #loading-container{
        position: fixed;
        top: 0;
        left: 0;
        min-height: 100vh;
        width: 100vw;
        z-index: 9999;
        display: flex;
        flex-direction: column;
        justify-content: center;
        align-items: center;
        background: #FFF;
        text-align: center;
        /* loaderҳ����ʧ���ý����ķ�ʽ*/
        -webkit-transition: opacity 1s ease;
        -moz-transition: opacity 1s ease;
        -o-transition: opacity 1s ease;
        transition: opacity 1s ease;
    }
    .loading-image{
        width: 120px;
        height: 50px;
        transform: translate(-50%);
    }

    .loading-image div:nth-child(2) {
        -webkit-animation: pacman-balls 1s linear 0s infinite;
        animation: pacman-balls 1s linear 0s infinite
    }

    .loading-image div:nth-child(3) {
        -webkit-animation: pacman-balls 1s linear .33s infinite;
        animation: pacman-balls 1s linear .33s infinite
    }

    .loading-image div:nth-child(4) {
        -webkit-animation: pacman-balls 1s linear .66s infinite;
        animation: pacman-balls 1s linear .66s infinite
    }

    .loading-image div:nth-child(5) {
        -webkit-animation: pacman-balls 1s linear .99s infinite;
        animation: pacman-balls 1s linear .99s infinite
    }

   .loading-image div:first-of-type {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_up .5s 0s infinite;
        animation: rotate_pacman_half_up .5s 0s infinite;
    }
    .loading-image div:nth-child(2) {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_down .5s 0s infinite;
        animation: rotate_pacman_half_down .5s 0s infinite;
        margin-top: -50px;
    }
    @-webkit-keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @-webkit-keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @-webkit-keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}

    @keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}


    .loading-image div:nth-child(3),
    .loading-image div:nth-child(4),
    .loading-image div:nth-child(5),
    .loading-image div:nth-child(6){
        background-color: #49b1f5;
        width: 15px;
        height: 15px;
        border-radius: 100%;
        margin: 2px;
        width: 10px;
        height: 10px;
        position: absolute;
        transform: translateY(-6.25px);
        top: 25px;
        left: 100px;
    }
    .loading-text{
        margin-bottom: 20vh;
        text-align: center;
        color: #2c3e50;
        font-size: 2rem;
        box-sizing: border-box;
        padding: 0 10px;
        text-shadow: 0 2px 10px rgba(0,0,0,0.2);
    }
    @media only screen and (max-width: 500px) {
         .loading-text{
            font-size: 1.5rem;
         }
    }
    .fadeout {
        opacity: 0;
        filter: alpha(opacity=0);
    }
    /* logo���ֶ��� */
    @-webkit-keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);transform:translate3d(0,-100%,0)}100%{opacity:1;-webkit-transform:none;transform:none}}
    @keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);}}
 </style>
 <script>
(function () {
    const loaded = function(){
       setTimeout(function(){
            const loader = document.getElementById("loading-container");
            loader.className="fadeout" ;//ʹ�ý����ķ�������loading page
            // document.getElementById("body-wrap").style.display="flex";
            setTimeout(function(){
                loader.style.display="none";
            },1000); 
        },1000);//ǿ����ʾloading page 1s  
    };
    loaded();
})()
 </script><link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"><style type="text/css" lang="css">
    #loading-container{
        position: fixed;
        top: 0;
        left: 0;
        min-height: 100vh;
        width: 100vw;
        z-index: 9999;
        display: flex;
        flex-direction: column;
        justify-content: center;
        align-items: center;
        background: #FFF;
        text-align: center;
        /* loaderҳ����ʧ���ý����ķ�ʽ*/
        -webkit-transition: opacity 1s ease;
        -moz-transition: opacity 1s ease;
        -o-transition: opacity 1s ease;
        transition: opacity 1s ease;
    }
    .loading-image{
        width: 120px;
        height: 50px;
        transform: translate(-50%);
    }

    .loading-image div:nth-child(2) {
        -webkit-animation: pacman-balls 1s linear 0s infinite;
        animation: pacman-balls 1s linear 0s infinite
    }

    .loading-image div:nth-child(3) {
        -webkit-animation: pacman-balls 1s linear .33s infinite;
        animation: pacman-balls 1s linear .33s infinite
    }

    .loading-image div:nth-child(4) {
        -webkit-animation: pacman-balls 1s linear .66s infinite;
        animation: pacman-balls 1s linear .66s infinite
    }

    .loading-image div:nth-child(5) {
        -webkit-animation: pacman-balls 1s linear .99s infinite;
        animation: pacman-balls 1s linear .99s infinite
    }

   .loading-image div:first-of-type {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_up .5s 0s infinite;
        animation: rotate_pacman_half_up .5s 0s infinite;
    }
    .loading-image div:nth-child(2) {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_down .5s 0s infinite;
        animation: rotate_pacman_half_down .5s 0s infinite;
        margin-top: -50px;
    }
    @-webkit-keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @-webkit-keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @-webkit-keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}

    @keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}


    .loading-image div:nth-child(3),
    .loading-image div:nth-child(4),
    .loading-image div:nth-child(5),
    .loading-image div:nth-child(6){
        background-color: #49b1f5;
        width: 15px;
        height: 15px;
        border-radius: 100%;
        margin: 2px;
        width: 10px;
        height: 10px;
        position: absolute;
        transform: translateY(-6.25px);
        top: 25px;
        left: 100px;
    }
    .loading-text{
        margin-bottom: 20vh;
        text-align: center;
        color: #2c3e50;
        font-size: 2rem;
        box-sizing: border-box;
        padding: 0 10px;
        text-shadow: 0 2px 10px rgba(0,0,0,0.2);
    }
    @media only screen and (max-width: 500px) {
         .loading-text{
            font-size: 1.5rem;
         }
    }
    .fadeout {
        opacity: 0;
        filter: alpha(opacity=0);
    }
    /* logo���ֶ��� */
    @-webkit-keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);transform:translate3d(0,-100%,0)}100%{opacity:1;-webkit-transform:none;transform:none}}
    @keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);}}
 </style>
 <script>
(function () {
    const loaded = function(){
       setTimeout(function(){
            const loader = document.getElementById("loading-container");
            loader.className="fadeout" ;//ʹ�ý����ķ�������loading page
            // document.getElementById("body-wrap").style.display="flex";
            setTimeout(function(){
                loader.style.display="none";
            },1000); 
        },1000);//ǿ����ʾloading page 1s  
    };
    loaded();
})()
 </script></head>


 <div id="loading-container">
     <p class="loading-text"></p> 
     <div class="loading-image">
         <div></div>
         <div></div>
         <div></div>
         <div></div> 
         <div></div>
     </div>
 </div><body>

    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">Shawlon`s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fa fa-navicon"></i></a>
<ul class="right">
    
    <li class="hide-on-med-and-down">
        <a href="/" class="waves-effect waves-light">
            
            <span>首页</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/tags" class="waves-effect waves-light">
            
            <span>标签</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/categories" class="waves-effect waves-light">
            
            <span>分类</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/archives" class="waves-effect waves-light">
            
            <span>归档</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/about" class="waves-effect waves-light">
            
            <span>关于</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/friends" class="waves-effect waves-light">
            
            <span>友情链接</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/contact" class="waves-effect waves-light">
            
            <span>留言板</span>
        </a>
    </li>
    
    <li>
        <a href="#searchModal" class="modal-trigger waves-effect waves-light">
            <i id="searchIcon" class="fa fa-search" title="搜索"></i>
        </a>
    </li>
</ul>

<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">Shawlon`s Blog</div>
        <div class="logo-desc">
            
            C++ | LeetCode | Algorithm
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li>
            <a href="/" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                首页
            </a>
        </li>
        
        <li>
            <a href="/tags" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                标签
            </a>
        </li>
        
        <li>
            <a href="/categories" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                分类
            </a>
        </li>
        
        <li>
            <a href="/archives" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                归档
            </a>
        </li>
        
        <li>
            <a href="/about" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                关于
            </a>
        </li>
        
        <li>
            <a href="/friends" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                友情链接
            </a>
        </li>
        
        <li>
            <a href="/contact" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                留言板
            </a>
        </li>
        
        
        <li><div class="divider"></div></li>
        <li>
            <a href="https://github.com/muyiio" class="waves-effect waves-light" target="_blank">
                <i class="fa fa-github-square fa-fw"></i>Fork Me
            </a>
        </li>
        
    </ul>
</div>

        </div>

        
            <style>
    .nav-transparent .github-corner {
        display: none !important;
    }

    .github-corner {
        position: absolute;
        z-index: 10;
        top: 0;
        right: 0;
        border: 0;
        transform: scale(1.1);
    }

    .github-corner svg {
        color: #0f9d58;
        fill: #fff;
        height: 64px;
        width: 64px;
    }

    .github-corner:hover .octo-arm {
        animation: a 0.56s ease-in-out;
    }

    .github-corner .octo-arm {
        animation: none;
    }

    @keyframes a {
        0%,
        to {
            transform: rotate(0);
        }
        20%,
        60% {
            transform: rotate(-25deg);
        }
        40%,
        80% {
            transform: rotate(10deg);
        }
    }
</style>

<a href="https://github.com/muyiio" class="github-corner tooltipped hide-on-med-and-down" target="_blank"
   data-tooltip="Fork Me" data-position="left" data-delay="50">
    <svg viewBox="0 0 250 250" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2"
              fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z"
              fill="currentColor" class="octo-body"></path>
    </svg>
</a>
        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('请输入访问本文章的密码')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/15.jpg')">
    <div class="container">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <div class="description center-align post-title">
                        暑假LeetCode刷题集合（上）
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>



<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        margin: 35px 0 15px 0;
        padding-left: 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #toc-content .is-active-link::before {
        background-color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 20px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                        <a href="/tags/LeetCode/" target="_blank">
                            <span class="chip bg-color">LeetCode</span>
                        </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fa fa-bookmark fa-fw icon-category"></i>
                        
                        <a href="/categories/每日一题/" class="post-category" target="_blank">
                            每日一题
                        </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                <div class="post-date info-break-policy">
                    <i class="fa fa-calendar-minus-o fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2021-06-27
                </div>

                <div class="post-author info-break-policy">
                    <i class="fa fa-user-o fa-fw"></i>作者:&nbsp;&nbsp;
                    
                    Tyzhao
                    
                </div>

                
                
                <div class="info-break-policy">
                    <i class="fa fa-file-word-o fa-fw"></i>文章字数:&nbsp;&nbsp;
                    5.5k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="fa fa-clock-o fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    25 分
                </div>
                
                

                
                <div id="busuanzi_container_page_pv" class="info-break-policy">
                    <i class="fa fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                    <span id="busuanzi_value_page_pv"></span>
                </div>
                
            </div>
        </div>
        <hr class="clearfix">
        <div class="card-content article-card-content">
            <div id="articleContent">
                <p><strong>最近决定巩固一下算法，开始刷leetcode每日一题，具体刷多久还不知道，刚开始是有点吃力，慢慢来。</strong></p>
<h2 id="【Day01】938-二叉搜索树的范围和"><a href="#【Day01】938-二叉搜索树的范围和" class="headerlink" title="【Day01】938.二叉搜索树的范围和"></a>【Day01】938.二叉搜索树的范围和</h2><p><strong>题目：</strong></p>
<p>给定二叉搜索树的根结点 <code>root</code>，返回值位于范围 <em><code>[low, high]</code></em> 之间的所有结点的值的和。</p>
<p><strong>示例1：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg" alt></p>
<pre><code>输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32</code></pre><p><strong>示例 2：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg" alt></p>
<pre><code>输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23</code></pre><p><strong>提示：</strong></p>
<ul>
<li>树中节点数目在范围 [1, 2 * 104] 内</li>
<li>1 &lt;= Node.val &lt;= 105</li>
<li>1 &lt;= low &lt;= high &lt;= 105</li>
<li>所有 Node.val 互不相同</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>递归</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        int sum = 0;
        sum += rangeSumBST(root->left, low, high);
        if (root->val >= low && root->val <= high) sum += root->val;
        sum += rangeSumBST(root->right, low, high);
        return sum;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>非递归</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        queue<TreeNode*> q;
        TreeNode* p = root;
        int sum = 0;
        while (p || q.size()) {
            while (p) {
                q.push(p);
                p = p->left;
            }
            if (q.size()) {
                p = q.front();
                q.pop();
                if (p->val >= low && p->val <= high) {
                    sum += p->val;
                }
                p = p->right;       
            }    
        }
        return sum;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day02】633-平方数之和"><a href="#【Day02】633-平方数之和" class="headerlink" title="【Day02】633.平方数之和"></a>【Day02】633.平方数之和</h2><p><strong>题目：</strong></p>
<p>给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：c = 3
输出：false</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：c = 4
输出：true</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：c = 2
输出：true</code></pre><p><strong>示例 5：</strong></p>
<pre><code>输入：c = 1
输出：true</code></pre><p><strong>枚举</strong></p>
<p>对 a 从 0 开始到 n√n 枚举，然后判断是否存在 b。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool judgeSquareSum(int c) {
        for (int i = 0; (long long)(i) * i <= c; i++) {
            int j = sqrt(c - i * i);
            if (i * i + j * j == c)
                return true;
        }
        return false;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>预处理+查询</strong></p>
<p>如果存在符合条件的a，b，那么a和b一定在1和sqrt(c)之间。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    typedef unsigned long long ULL;
    bool judgeSquareSum(int c) {
        if (c == 0) return true;
        unordered_map<ULL, ULL> um;
        for (int i = 1; i <= sqrt(c); i++) {
            um[i*i]++;
        }

        for (int i = 1; i <= sqrt(c); i++) {
            if (i*i == c || um.count(c - i*i)) return true;
        }
        return false;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>双指针</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool judgeSquareSum(int c) {
        int j = sqrt(c);
        int i = 0;
        while (i <= j) {
            if (i*i > c - j*j) {
                j--;
            } else if (i*i < c - j*j) {
                i++;
            } else {
                return true;
            }
        }
        return false;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day03】403-青蛙过河"><a href="#【Day03】403-青蛙过河" class="headerlink" title="【Day03】403.青蛙过河"></a>【Day03】403.青蛙过河</h2><h3 id="403-青蛙过河"><a href="#403-青蛙过河" class="headerlink" title="403. 青蛙过河"></a><a href="https://leetcode-cn.com/problems/frog-jump/" target="_blank" rel="noopener">403. 青蛙过河</a></h3><p><strong>题目描述：</strong></p>
<p>一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。</p>
<p>给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。</p>
<p>开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。</p>
<p>如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。</p>
<p>  <strong>示例 1：</strong></p>
<pre><code>输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>2 &lt;= stones.length &lt;= 2000</li>
<li>0 &lt;= stones[i] &lt;= 231 - 1</li>
<li>stones[0] == 0</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>递归:</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    unordered_map<int, int> um;
    bool canCross(vector<int>& stones) {

        for (int i = 0; i < stones.size(); i++) {
            um[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if (!um.count(1)) return false;
        return dfs(stones, stones.size(), 1, 1);
    }
    bool dfs(vector<int>& stones, int n, int cur, int k) {
        if (cur == n - 1) return true;
        for (int i = -1; i <= 1; i++) {
            if (k + i == 0) continue;
            int next = stones[cur] + k + i;
            if (um.count(next)) { // 存在
                bool choose = dfs(stones, n, um[next], k + i);
                if (choose) return true;
            }
        }
        return false;
    }

};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>dfs记忆化搜索:</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    unordered_map<int, int> um;
    vector<vector<int>> memo;
    bool canCross(vector<int>& stones) {

        for (int i = 0; i < stones.size(); i++) {
            um[stones[i]] = i;  // key:石子值 value是第几块石子
        }
        if (!um.count(1)) return false;
        memo = vector<vector<int>>(stones.size(), vector<int>(stones.size(), -1));
        return dfs(stones, stones.size(), 1, 1);
    }
    bool dfs(vector<int>& stones, int n, int cur, int k) {
        if (memo[cur][k] != -1) return memo[cur][k];
        if (cur == n - 1) return memo[cur][k] = true;
        for (int i = -1; i <= 1; i++) {
            if (k + i == 0) continue;  // 原地跳过
            int next = stones[cur] + k + i;
            if (um.count(next)) { // 存在
                bool choose = dfs(stones, n, um[next], k + i);
                if (choose) return memo[cur][k] = true;
            }
        }
        return memo[cur][k] = false;
    }

};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>动态规划：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if (stones[1] != 1) return false;
        vector<vector<bool>> dp(n, vector<bool>(n));
        // dp[i][k] 表示在第i个位置且跳k个单位到第i块石子。
        dp[1][1] = true;
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                int k = stones[i] - stones[j];
                if (k > j + 1) continue;
                // 因为题目要求 青蛙第一次只能跳1步，那么第二次至多跳2步，以此类推，青蛙在第i块（i从0开始）石头上至多只能跳i+1步。在第j块石头上至多只能跳 j+1 步 ，如果k > j+1，说明石头 i 隔石头 j 太远了，远到不满足题目的隐藏规则，所以青蛙必定跳不过去。
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k+1];
            }
        }
        for (int i = 1; i < n; i++) {
            if (dp[n-1][i]) return true;
        }        
        return false;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>另一种动态规划:</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool canCross(vector<int>& stones) {
        // dp[i][j] 表示 第 i 个石头是否可以跳 j 步
        int n = stones.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        dp[0][1] = true;
        for (int i = 1; i < n; i++) {
            bool flag = false;
            for (int j = i - 1; j >= 0; j--) {
                int k = stones[i] - stones[j];
                if (k > i) break;
                if (dp[j][k]) {
                    dp[i][k - 1] = dp[i][k] = dp[i][k + 1] = true;
                    flag = true;
                }
            }
            if (i == n - 1 && !flag) {
                return false;
            }
        }
        return true;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day04】137-只出现一次的数字II"><a href="#【Day04】137-只出现一次的数字II" class="headerlink" title="【Day04】137.只出现一次的数字II"></a>【Day04】137.只出现一次的数字II</h2><h4 id="137-只出现一次的数字-II"><a href="#137-只出现一次的数字-II" class="headerlink" title="137. 只出现一次的数字 II"></a><a href="https://leetcode-cn.com/problems/single-number-ii/" target="_blank" rel="noopener">137. 只出现一次的数字 II</a></h4><p>给你一个整数数组 <code>nums</code> ，除某个元素仅出现 <strong>一次</strong> 外，其余每个元素都恰出现 <strong>三次 。</strong>请你找出并返回那个只出现了一次的元素。</p>
<p> <strong>示例1：</strong></p>
<pre><code>输入：nums = [2,2,3,2]
输出：3</code></pre><p><strong>示例2：</strong></p>
<pre><code>输入：nums = [0,1,0,1,0,1,99]
输出：99</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= nums.length &lt;= 3 * 104</li>
<li>-231 &lt;= nums[i] &lt;= 231 - 1</li>
<li>nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次</li>
</ul>
<p><strong>题解：</strong></p>
<p> <strong>有限状态自动机：</strong></p>
<p>使用二进制表示每个元素，对应二进制位的1相加，最后相加对3取余</p>
<p>对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0,1,2 。由于二进制只能表示 0, 10,1 ，因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 one，two.</p>
<p><strong>计算 one方法：</strong></p>
<p>设当前状态为 one ，two 此时输入二进制位 nn 。如下图所示，通过对状态表的情况拆分，可推出 one的计算方法为：</p>
<pre><code>if two == 0:
  if n == 0:
    one = one
  if n == 1:
    one = ~one
if two == 1:
    one = 0</code></pre><p>引入 异或运算 ，可将以上拆分简化为：</p>
<pre><code>if two == 0:
    one = one ^ n
if two == 1:
    one = 0</code></pre><p>引入 与运算 ，可继续简化为：</p>
<pre><code>one = one ^ n &amp; ~two</code></pre><p>同理：</p>
<pre><code>two = two ^ n &amp; ~one</code></pre><p>代码：</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int two = 0, one = 0;
        for (auto x: nums) {
            one = (one ^ x) & ~two;
            two = (two ^ x) & ~one;
        }
        return one;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>哈希表：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> um;
        for (auto x : nums) {
            um[x]++;
        }

        for (auto x : um) {
            if (x.second == 1) return x.first;
        }
        return -1;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day05】690-员工的重要性"><a href="#【Day05】690-员工的重要性" class="headerlink" title="【Day05】690.员工的重要性"></a>【Day05】690.员工的重要性</h2><h4 id="690-员工的重要性"><a href="#690-员工的重要性" class="headerlink" title="690. 员工的重要性"></a><a href="https://leetcode-cn.com/problems/employee-importance/" target="_blank" rel="noopener">690. 员工的重要性</a></h4><p>给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。</p>
<p>比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。</p>
<p>现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。</p>
<p><strong>示例：</strong></p>
<pre><code>输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>一个员工最多有一个 直系 领导，但是可以有多个 直系 下属</li>
<li>员工数量不超过 2000 。</li>
</ul>
<p><strong>题解：</strong></p>
<p>今天的题不是很难，直接遍历所有节点相加就行了，使用哈希表将id指向映射到指针，遍历一遍。</p>
<p><strong>dfs</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    unordered_map<int, Employee*> hash;

    int getImportance(vector<Employee*> employees, int id) {
        for (auto& p: employees) hash[p->id] = p;
        return dfs(id);
    }

    int dfs(int id) {
        auto p = hash[id];
        int res = p->importance;
        for (auto son: p->subordinates)
            res += dfs(son);
        return res;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day06】554-砖墙"><a href="#【Day06】554-砖墙" class="headerlink" title="【Day06】554.砖墙"></a>【Day06】554.砖墙</h2><h4 id="554-砖墙"><a href="#554-砖墙" class="headerlink" title="554. 砖墙"></a><a href="https://leetcode-cn.com/problems/brick-wall/" target="_blank" rel="noopener">554. 砖墙</a></h4><p>你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。</p>
<p>你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。</p>
<p>给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。</p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2021/04/24/cutwall-grid.jpg" alt></p>
<pre><code>输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：wall = [[1],[1],[1]]
输出：3</code></pre><p><strong>提示：</strong></p>
<ul>
<li>n == wall.length</li>
<li>1 &lt;= n &lt;= 104</li>
<li>1 &lt;= wall[i].length &lt;= 104</li>
<li>1 &lt;= sum(wall[i].length) &lt;= 2 * 104</li>
<li>对于每一行 i ，sum(wall[i]) 应当是相同的</li>
<li>1 &lt;= wall[i][j] &lt;= 231 - 1</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>贪心，哈希表</strong></p>
<p>显然最优的线一定是沿某个块砖的边缘穿过的。<br>统计每一行的砖可以从左到右可以构成的长度值，用 unordered_map 哈希表统计长度值出现的次数。出现次数最多的值就应该是这条线所在的位置。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> cnt;
        for (auto& line: wall) {
            for (int i = 0, s = 0; i + 1 < line.size(); i ++ ) {
                s += line[i];
                cnt[s] ++ ;
            }
        }
        int res = 0;
        for (auto [k, v]: cnt) res = max(res, v);
        return wall.size() - res;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day07】7-整数反转7-整数反转"><a href="#【Day07】7-整数反转7-整数反转" class="headerlink" title="【Day07】7.整数反转7. 整数反转"></a>【Day07】7.整数反转<a href="https://leetcode-cn.com/problems/reverse-integer/" target="_blank" rel="noopener">7. 整数反转</a></h2><p>给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。</p>
<p>如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。</p>
<p>假设环境不允许存储 64 位整数（有符号或无符号）。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：x = 123
输出：321</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：x = -123
输出：-321</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：x = 120
输出：21</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：x = 0
输出：0</code></pre><p><strong>提示：</strong></p>
<ul>
<li>-231 &lt;= x &lt;= 231 - 1</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>(循环) O(logn)</strong><br>依次从右往左计算出每位数字，然后逆序累加在一个整数中。<br>另外，这题有两点需要注意：</p>
<ul>
<li><p>因为int型整数逆序后可能会溢出，所以我们要用long long记录中间结果；</p>
</li>
<li><p>在C++中，负数的取模运算和数学意义上的取模运算不同，结果还是负数，比如 −12%10=−2−12%10=−2，所以我们不需要对负数进行额外处理。</p>
</li>
</ul>
<p>时间复杂度分析：一共有 O(logn) 位，对于每一位的计算量是常数级的，所以总时间复杂度是  O(logn)</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x) {
            if (x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
            if (x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day08】1473-粉刷房子III"><a href="#【Day08】1473-粉刷房子III" class="headerlink" title="【Day08】1473.粉刷房子III"></a>【Day08】1473.粉刷房子III</h2><h4 id="1473-粉刷房子-III"><a href="#1473-粉刷房子-III" class="headerlink" title="1473. 粉刷房子 III"></a><a href="https://leetcode-cn.com/problems/paint-house-iii/" target="_blank" rel="noopener">1473. 粉刷房子 III</a></h4><p>在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。</p>
<p>我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区  [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）</p>
<p>给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：</p>
<ul>
<li>houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。</li>
<li>cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。</li>
</ul>
<p>请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>m == houses.length == cost.length</li>
<li>n == cost[i].length</li>
<li>1 &lt;= m &lt;= 100</li>
<li>1 &lt;= n &lt;= 20</li>
<li>1 &lt;= target &lt;= m</li>
<li>0 &lt;= houses[i] &lt;= n</li>
<li>1 &lt;= cost[i][j] &lt;= 10^4</li>
</ul>
<p><strong>题解·：</strong></p>
<p>很明显的DP</p>
<ol>
<li><p>设状态  f(i,j,k) 表示处理了前 i 个房屋，有 j 个社区，最后一个房屋的颜色为 k 的最小花费，其中房屋的有效下标从 1 开始。建立辅助数组 g(i,j,k) 表示同样含义下，最后一个房屋颜色 不是 k 的最小花费。</p>
</li>
<li><p>初始时，f(0,0,k)=g(0,0,k)=0，其余为正无穷或者待定。<br>转移时，分两种情况</p>
</li>
<li><p>如果第 i 个房屋已经有了颜色 c，则有两种选择，上一个房屋颜色为 c 或者不为 c，转移<br>$$<br>f(i, j, c)=\min (f(i-1, j, c), g(i-1, j-1, c))<br>$$</p>
</li>
<li><p>如果第 i 个房屋没有颜色，则枚举一个颜色 k，然后同样根据上一个房屋的颜色，转移<br>$$<br>f(i, j, k)=\min (f(i-1, j, k), g(i-1, j-1, k))+\operatorname{cost}(i, k-1)_{\text {。 }}<br>$$</p>
</li>
<li><p>对于 g 数组的维护如下，假设当前需要维护前 i 个房屋且有 j 个社区下的 g 数组，则我们找 f(i,j,k) 中的最小值 m1 和次小值 m2。如果 m1=m2，则说明对于所有 k， g(i,j,k)=m1；否则，对于 f(i,j,k0)=m1 的那个 k0，其 g(i,j,k0)=m2g，其余 k≠k0都有 g(i,j,k)=m1。</p>
</li>
<li><p>最终答案为<br>$$<br>\min (f(m, \text { target }, k)<br>$$</p>
</li>
</ol>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int MAX = 0x3f3f3f3f;
        const int M = 110;
        const int N = 30;

        int f[M][M][N], g[M][M][N];
        memset(f, 0x3f, sizeof(f));
        memset(g, 0x3f, sizeof(g));

        for (int k = 1; k <= n; k++)
            f[0][0][k] = g[0][0][k] = 0;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= min(i, target); j++) {
                if (houses[i - 1] > 0) {
                    int c = houses[i - 1];
                    f[i][j][c] = min(f[i - 1][j][c], g[i - 1][j - 1][c]);
                } else {
                    for (int k = 1; k <= n; k++)
                        f[i][j][k] = min(f[i - 1][j][k], g[i - 1][j - 1][k])
                                        + cost[i - 1][k - 1];
                }

                int m1 = MAX, m2 = MAX;
                for (int k = 1; k <= n; k++)
                    if (m1 > f[i][j][k]) {
                        m2 = m1;
                        m1 = f[i][j][k];
                    } else if (m2 > f[i][j][k])
                        m2 = f[i][j][k];

                if (m1 == m2) {
                    for (int k = 1; k <= n; k++)
                        g[i][j][k] = m1;
                } else {
                    for (int k = 1; k <= n; k++)
                        if (f[i][j][k] == m1) g[i][j][k] = m2;
                        else g[i][j][k] = m1;
                }
            }

        int ans = MAX;
        for (int k = 1; k <= n; k++)
            ans = min(ans, f[m][target][k]);

        if (ans == MAX)
            ans = -1;

        return ans;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day09】740-删除并获得点数"><a href="#【Day09】740-删除并获得点数" class="headerlink" title="【Day09】740.删除并获得点数"></a>【Day09】740.删除并获得点数</h2><h4 id="740-删除并获得点数-https-leetcode-cn-com-problems-delete-and-earn"><a href="#740-删除并获得点数-https-leetcode-cn-com-problems-delete-and-earn" class="headerlink" title="740. 删除并获得点数](https://leetcode-cn.com/problems/delete-and-earn/)"></a>740. 删除并获得点数](<a href="https://leetcode-cn.com/problems/delete-and-earn/" target="_blank" rel="noopener">https://leetcode-cn.com/problems/delete-and-earn/</a>)</h4><p>给你一个整数数组 nums ，你可以对它进行一些操作。</p>
<p>每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。</p>
<p>开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= nums.length &lt;= 2 * 104</li>
<li>1 &lt;= nums[i] &lt;= 104</li>
</ul>
<p><strong>题解：</strong></p>
<p>首先，我们先明确一个概念，就是每个位置上的数字是可以在两种前结果之上进行选择的：</p>
<p>如果你不删除当前位置的数字，那么你得到就是前一个数字的位置的最优结果。<br>如果你觉得当前的位置数字i需要被删，那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。<br>以上两个结果，你每次取最大的，记录下来，然后答案就是最后那个数字了。</p>
<p>如果你看到现在有点迷糊，那么我们先把数字进行整理一下。</p>
<p>我们在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。</p>
<p>举个例子：</p>
<pre><code>nums = [2, 2, 3, 3, 3, 4]</code></pre><p>构造后：</p>
<pre><code>all=[0, 0, 2, 3, 1];</code></pre><p>就是代表着 22 的个数有两个，33 的个数有 33 个，44 的个数有 11 个。</p>
<p>其实这样就可以变成打家劫舍的问题了呗。</p>
<p>我们来看看，打家劫舍的最优子结构的公式：</p>
<p>$$<br>\mathrm{dp}[\mathrm{i}]=\text { Math.max }(\mathrm{d} \mathrm{p}[\mathrm{i}-1], \mathrm{dp}[\mathrm{i}-2]+\mathrm{nums}[\mathrm{i}])<br>$$<br>再来看看现在对这个问题的最优子结构公式：</p>
<p>$$<br>\mathrm{dp}[\mathrm{i}]=\text { Math.max }\left(\mathrm{dp}[\mathrm{i}-1], \mathrm{dp}[\mathrm{i}-2]+\mathrm{i}^{\star} \mathrm{all}[\mathrm{i}]\right)<br>$$</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        int maxn = 0;
        for(int it : nums)
            maxn = max(maxn, it);
        vector<int> cnt(maxn+1), dp(maxn+1);
        for(int it : nums)
            cnt[it]++;
        dp[1] = cnt[1];
        for(int i = 2; i <= maxn; i++)
            dp[i] = max(dp[i-1], dp[i-2] + cnt[i] * i);
        return dp[maxn];
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day10】1720-解码异或后的数组"><a href="#【Day10】1720-解码异或后的数组" class="headerlink" title="【Day10】1720. 解码异或后的数组"></a>【Day10】1720. 解码异或后的数组</h2><h4 id="1720-解码异或后的数组"><a href="#1720-解码异或后的数组" class="headerlink" title="1720. 解码异或后的数组"></a><a href="https://leetcode-cn.com/problems/decode-xored-array/" target="_blank" rel="noopener">1720. 解码异或后的数组</a></h4><p>未知 整数数组 arr 由 n 个非负整数组成。</p>
<p>经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。</p>
<p>给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。</p>
<p>请解码返回原数组 arr 。可以证明答案存在并且是唯一的。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]</code></pre><p><strong>提示：</strong></p>
<ul>
<li>2 &lt;= n &lt;= 104</li>
<li>encoded.length == n - 1</li>
<li>0 &lt;= encoded[i] &lt;= 105</li>
<li>0 &lt;= first &lt;= 105</li>
</ul>
<p><strong>题解：</strong></p>
<p>异或运算满足交换律和结合律；</p>
<p>任意整数和自身做异或运算的结果都等于 0，即 x⊕x=0；</p>
<p>任意整数和 0 做异或运算的结果都等于其自身，即 x⊕0=0⊕x=x。</p>
<p>在等号两边同时异或 arr[i]</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        int n = encoded.size();
        vector<int> arr(n + 1);
        arr[0] = first;
        for (int i = 0; i < n; i ++)
            arr[i + 1] = arr[i] ^ encoded[i];
        return arr;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day11】1486-数组异或操作"><a href="#【Day11】1486-数组异或操作" class="headerlink" title="【Day11】1486.数组异或操作"></a>【Day11】1486.数组异或操作</h2><h4 id="1486-数组异或操作"><a href="#1486-数组异或操作" class="headerlink" title="1486. 数组异或操作"></a><a href="https://leetcode-cn.com/problems/xor-operation-in-an-array/" target="_blank" rel="noopener">1486. 数组异或操作</a></h4><p>给你两个整数，n 和 start 。</p>
<p>数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。</p>
<p>请返回 nums 中所有元素按位异或（XOR）后得到的结果。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     &quot;^&quot; 为按位异或 XOR 运算符。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：n = 1, start = 7
输出：7</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：n = 10, start = 5
输出：2</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= n &lt;= 1000</li>
<li>0 &lt;= start &lt;= 1000</li>
<li>n == nums.length</li>
</ul>
<p><strong>题解：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int xorOperation(int n, int start)
    {
        int result = start, i;
        for (i = 1; i < n; i++)
        {
            result = result ^ (start + i * 2);
        }
        return result;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day12】1723-完成所有工作的最短时间"><a href="#【Day12】1723-完成所有工作的最短时间" class="headerlink" title="【Day12】1723.完成所有工作的最短时间"></a>【Day12】1723.完成所有工作的最短时间</h2><h4 id="1723-完成所有工作的最短时间"><a href="#1723-完成所有工作的最短时间" class="headerlink" title="1723. 完成所有工作的最短时间"></a><a href="https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/" target="_blank" rel="noopener">1723. 完成所有工作的最短时间</a></h4><p>给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。</p>
<p>请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。</p>
<p>返回分配方案中尽可能 最小 的 最大工作时间 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= k &lt;= jobs.length &lt;= 12</li>
<li>1 &lt;= jobs[i] &lt;= 107</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>回溯法+剪枝</strong></p>
<p>用一个 vector<int> block 记录每个人分配到的工作量，尝试将一份工作分配给一个人，且它的工作时间不超过lim要求，之后开启递归分配下一项工作，尝试找到一个成功分配全部工作的路径</int></p>
<p>递归深度为 n=jobs.length 工作数量，每次递归需要检测范围为 k 员工数量并开启分支，最坏情况下走满树时间复杂度为 O(k^n)<br>题设 1 &lt;= k &lt;= jobs.length &lt;= 12，最坏情况下 12^12 = 8.9E12，外面还套了一个二分，还要再乘 log12 = 3.xxxx，远超1s极限算量1E8</p>
<p>因此我们需要考虑一些剪枝的方法，首先我们可以 sort 一下 jobs ，时长从大到小开始分配，进而能够更快的超出限制，被剪枝掉，其次是朴素写法中存在很多重复的路径</p>
<p>例如对于第一份工作的分配，所有人工作时长全部是0，我们只需要分配一次</p>
<pre><code>[t1,0,0,0,0]
之后的
[0,t1,0,0,0]
...</code></pre><p>都是重复操作。</p>
<p> 56号测试用例：</p>
<pre><code>[5,5,4,4,4]
2</code></pre><p>如果先将 5h 分配给两个人block [5,5]，之后分配4时，只需要走一次 [9,5]，后面的[5,9] 是重复操作</p>
<p>由于jobs已排序，因此我们每次枚举到的 block[i] 应当和上一次不一样，才是没走过的路径，进而排除全0时的重复放置，或是出现相同工作时长分配时的重复放置</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int k;
    vector<int>  block;
    bool backtracking(vector<int>& jobs,int id,int lim) {
        if(id==-1) return true; //出口 全部放完了

        bool res=false;
        int last=INT_MIN; 

        for(int i=0;i<k;++i) {
            if(res) 
                break;
            if(block[i]==last) 
                continue; //剪枝 因为jobs已排序所以应枚举和上一次不一样的结果

            last=block[i];

            if(block[i]<=lim-jobs[id]){ //小心越界
                block[i]+=jobs[id];
                res = backtracking(jobs,id-1,lim);
                block[i]-=jobs[id];
            }
        }
        return res;
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        this->k = k;
        int s=0; //区间左端点（最小）
        int e=0; //区间右端点（最大）
        int m;//中间
        int n = jobs.size()-1;//起手下标
        block = vector<int>(k,0); // 拷贝初始化
        sort(jobs.begin(),jobs.end());    
        s=jobs[n];//结果最小应是 jobs[i] 的最大值

        for(auto i : jobs) { //最大应是 sum(jobs.begin(),jobs.end()) 小心越界
            if(e<=INT_MAX-i) e+=i;
            else e=INT_MAX;
        }        
        while(s!=e) {
            int m = (s+e)/2;
            if(backtracking(jobs,n,m)) { //成功 尝试缩减区间
                e=m;//m无法排除
            }else {//失败 扩大
                s=m+1;//m肯定不对最少加1
            }
        }
        return s;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day13】1482-制作m束花所需的最少天数"><a href="#【Day13】1482-制作m束花所需的最少天数" class="headerlink" title="【Day13】1482.制作m束花所需的最少天数"></a>【Day13】1482.制作m束花所需的最少天数</h2><h4 id="1482-制作-m-束花所需的最少天数"><a href="#1482-制作-m-束花所需的最少天数" class="headerlink" title="1482. 制作 m 束花所需的最少天数"></a><a href="https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets/" target="_blank" rel="noopener">1482. 制作 m 束花所需的最少天数</a></h4><p>给你一个整数数组 bloomDay，以及两个整数 m 和 k 。</p>
<p>现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。</p>
<p>花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。</p>
<p>请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束</code></pre><p><strong>示例 5：</strong></p>
<pre><code>输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9</code></pre><p><strong>提示：</strong></p>
<ul>
<li>bloomDay.length == n</li>
<li>1 &lt;= n &lt;= 10^5</li>
<li>1 &lt;= bloomDay[i] &lt;= 10^9</li>
<li>1 &lt;= m &lt;= 10^6</li>
<li>1 &lt;= k &lt;= n</li>
</ul>
<p><strong>题解：</strong></p>
<p>假设制作m束花需要等待的最少天数是x天，那么有：</p>
<ul>
<li>[0, x)天无法制作出来m束</li>
<li>[x,maxDay]可以制作出m束</li>
</ul>
<p>求出给定花开数组中最大值，进行二分计算即可。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if (m * k  > n) return -1;
        int l = 0, r = 0;
        for (auto x : bloomDay) {
            r = max(r, x);
        }
        while(l < r) {
            int mid = l + r >> 1;
            if (check(bloomDay, mid, m, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    bool check(vector<int>& bloomDay, int mid, int m, int k) {
        int sum = 0;
        // 计算是否满足m束花且每一束都有相邻的k个
        for (int i = 0; i < bloomDay.size() && sum < m; i++) {
            int cur_sum = 0;
            if (bloomDay[i] <= mid) { // 可以开
                cur_sum++;
                int j = i + 1;
                while (j < bloomDay.size() && bloomDay[j] <= mid && cur_sum < k) {
                    j++;
                    cur_sum++;
                }
                if (cur_sum == k) sum++;
                i = j - 1;
            } 
        }
        return sum >= m;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day14】872-叶子相似的树"><a href="#【Day14】872-叶子相似的树" class="headerlink" title="【Day14】872.叶子相似的树"></a>【Day14】872.叶子相似的树</h2><h4 id="872-叶子相似的树"><a href="#872-叶子相似的树" class="headerlink" title="872. 叶子相似的树"></a><a href="https://leetcode-cn.com/problems/leaf-similar-trees/" target="_blank" rel="noopener">872. 叶子相似的树</a></h4><p>请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 <em>叶值序列</em> 。</p>
<p><img src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/16/tree.png" alt></p>
<p>举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。</p>
<p>如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。</p>
<p>如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。</p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-1.jpg" alt></p>
<pre><code>输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：root1 = [1], root2 = [1]
输出：true</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：root1 = [1], root2 = [2]
输出：false</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：root1 = [1,2], root2 = [2,2]
输出：true</code></pre><p><strong>示例 5：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/09/03/leaf-similar-2.jpg" alt></p>
<pre><code>输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false</code></pre><p><strong>提示：</strong></p>
<ul>
<li>给定的两棵树可能会有 1 到 200 个结点。</li>
<li>给定的两棵树上的值介于 0 到 200 之间。</li>
</ul>
<p><strong>题解：</strong></p>
<p>将第一次的结果存储下来后，后面直接比较并返回结果。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int index = 0;
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> r1;
        dfs1(root1, r1);
        return dfs2(root2, r1) && index == r1.size();
    }
    void dfs1(TreeNode* root, vector<int>& res) {
        if (!root) return;
        if (!root->left && !root->right) {
            res.push_back(root->val);
            return;
        }
        dfs1(root->left, res);
        dfs1(root->right, res);
    }
    bool dfs2(TreeNode* root, vector<int>& res) {
        if (!root) return true;
        if (!root->left && !root->right) {
            if (index >= res.size()) return false;
            if (root->val != res[index]) return false;
            index++;
            return true;
        }
        return dfs2(root->left, res) && dfs2(root->right, res);
    }

};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day15】1734-解码异或后的排列"><a href="#【Day15】1734-解码异或后的排列" class="headerlink" title="【Day15】1734.解码异或后的排列"></a>【Day15】1734.解码异或后的排列</h2><h4 id="1734-解码异或后的排列"><a href="#1734-解码异或后的排列" class="headerlink" title="1734. 解码异或后的排列"></a><a href="https://leetcode-cn.com/problems/decode-xored-permutation/" target="_blank" rel="noopener">1734. 解码异或后的排列</a></h4><p>给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。</p>
<p>它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。</p>
<p>给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]</code></pre><p><strong>提示：</strong></p>
<ul>
<li>3 &lt;= n &lt; 105</li>
<li>n 是奇数。</li>
<li>encoded.length == n - 1</li>
</ul>
<p><strong>题解：</strong></p>
<p>perm = [A,B,C,D,E]</p>
<p>encoded = [A^B, B^C, C^D, D^E]</p>
<p>而B^C^D^E = encoded[1] ^ encode[3]</p>
<p>A^B^C^D^E = total</p>
<p>total ^ (B^C^D^E) = first</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        int total = 0;
        for (int i = 1; i <= n; i++) {
            total ^= i;
        }

        int e = 0;
        for (int i = 1; i < n - 1; i += 2) {
            e ^= encoded[i];
        }

        vector<int> ans(n);
        ans[0] = total ^ e;
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i-1] ^ encoded[i-1];
        }
        return ans;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day16】1310-子数组异或查询"><a href="#【Day16】1310-子数组异或查询" class="headerlink" title="【Day16】1310.子数组异或查询"></a>【Day16】1310.子数组异或查询</h2><h4 id="1310-子数组异或查询"><a href="#1310-子数组异或查询" class="headerlink" title="1310. 子数组异或查询"></a><a href="https://leetcode-cn.com/problems/xor-queries-of-a-subarray/" target="_blank" rel="noopener">1310. 子数组异或查询</a></h4><p>有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。</p>
<p>对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。</p>
<p>并返回一个包含给定查询 queries 所有结果的数组。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8] 
解释：
数组中元素的二进制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= arr.length &lt;= 3 * 10^4</li>
<li>1 &lt;= arr[i] &lt;= 10^9</li>
<li>1 &lt;= queries.length &lt;= 3 * 10^4</li>
<li>queries[i].length == 2</li>
<li>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt; arr.length</li>
</ul>
<p><strong>题解：</strong></p>
<p>利用前缀和思想：sum(i,j) = sum(j) - sum(i-1);</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> ans;
        int sum[arr.size() + 1];
        for (int i = 1; i <= arr.size(); i++) {
            sum[i] = sum[i - 1] ^ arr[i - 1];
        }

        for (auto q : queries) {
            ans.push_back(sum[q[1] + 1] ^ sum[q[0]]);
        }
        return ans;
    }<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day17】1269-停在原地的方案数"><a href="#【Day17】1269-停在原地的方案数" class="headerlink" title="【Day17】1269.停在原地的方案数"></a>【Day17】1269.停在原地的方案数</h2><h4 id="1269-停在原地的方案数"><a href="#1269-停在原地的方案数" class="headerlink" title="1269. 停在原地的方案数"></a><a href="https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/" target="_blank" rel="noopener">1269. 停在原地的方案数</a></h4><p>有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。</p>
<p>每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。</p>
<p>给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。</p>
<p>由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动</code></pre><p><strong>示例  2：</strong></p>
<pre><code>输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：steps = 4, arrLen = 2
输出：8</code></pre><p><strong>提示：</strong></p>
<pre><code>1 &lt;= steps &lt;= 500
1 &lt;= arrLen &lt;= 10^6</code></pre><p><strong>题解：</strong></p>
<p><strong>暴力递归</strong></p>
<p>pos表示移动的index,st表示当前还剩步数。结果超时- _ -</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
 public:
  const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      int res = dfs(steps, arrLen, 0);
      return res % N; 
  }

  int dfs(int st, int arrLen, int pos) {
    if (st < 0 || pos < 0 || pos >= arrLen) return 0;
    if (st == 0 && pos == 0) {
      return 1;
    }
    int ans = 0;
    if (pos >= 0 && pos <= arrLen - 1)
      // 不动
      ans = dfs(st - 1, arrLen, pos);
    if (pos >= 1)
      // 向左
      ans += dfs(st - 1, arrLen, pos - 1);
    if (pos <= arrLen - 2)
      // 向右
      ans += dfs(st- 1, arrLen, pos + 1);
    return ans;
  }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>记忆化搜索</strong></p>
<p><strong>一开始开辟空间太大，过不了，发现开辟很大空间后，使用map性能比vector好，而实际只需要开辟steps*steps即可。</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">int memo[505][505];
// vector<vector<int>> memo;
class Solution {
 public:
  static const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      memset(memo, -1, sizeof(memo));
    //   memo = vector<vector<int>>(505, vector<int>(505,-1));
      int res = dfs(steps, arrLen, 0);
      return res % N; 
  }

  int dfs(int st, int arrLen, int pos) {
    if (st < 0 || pos < 0 || pos >= arrLen) return 0;
    if (memo[st][pos] != -1) return memo[st][pos];
    if (st == 0 && pos == 0) {
      return memo[st][pos] = 1;
    }
    int ans = 0;
    if (pos >= 0 && pos <= arrLen - 1) 
      // 不动
      ans = dfs(st - 1, arrLen, pos) % N;
    if (pos >= 1)
      // 向左
      ans =  ans % N + dfs(st - 1, arrLen, pos - 1) % N;
    if (pos <= arrLen - 2)
      // 向右
      ans = ans % N + dfs(st- 1, arrLen, pos + 1) % N;
    return memo[st][pos] = ans;
  }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>动态规划</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
 public:
  static const int N = 1000000007;
  int numWays(int steps, int arrLen) { 
      int maxLen = min(steps, arrLen);
      long long dp[steps + 1][maxLen + 1];
      memset(dp, 0, sizeof dp);
      dp[1][0] = 1;
      dp[1][1] = 1; // step=1 pos=1

      for (int s = 1; s <= steps; s++) {
          for (int l = 0; l < maxLen; l++) {
            // 原地
                dp[s][l] = dp[s][l] + dp[s - 1][l];
            // 右
                dp[s][l] = dp[s][l]  + dp[s - 1][l + 1];
            // 左

                if (l - 1 >= 0)
                    dp[s][l] =  dp[s][l] + dp[s - 1][l - 1];

              dp[s][l] %= N;
          }
      }     
      return dp[steps][0]; 
  }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day18】12-整数转罗马数字"><a href="#【Day18】12-整数转罗马数字" class="headerlink" title="【Day18】12.整数转罗马数字"></a>【Day18】12.整数转罗马数字</h2><h4 id="12-整数转罗马数字"><a href="#12-整数转罗马数字" class="headerlink" title="12. 整数转罗马数字"></a><a href="https://leetcode-cn.com/problems/integer-to-roman/" target="_blank" rel="noopener">12. 整数转罗马数字</a></h4><p>罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。</p>
<pre><code>字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000</code></pre><blockquote>
<p>例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。</p>
</blockquote>
<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：</p>
<ul>
<li>I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。</li>
<li>X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 </li>
<li>C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。</li>
</ul>
<p>给你一个整数，将其转为罗马数字。</p>
<p><strong>示例 1:</strong></p>
<pre><code>输入: num = 3
输出: &quot;III&quot;</code></pre><p><strong>示例 2:</strong></p>
<pre><code>输入: num = 4
输出: &quot;IV&quot;</code></pre><p><strong>示例 3:</strong></p>
<pre><code>输入: num = 9
输出: &quot;IX&quot;</code></pre><p><strong>示例 4:</strong></p>
<pre><code>输入: num = 58
输出: &quot;LVIII&quot;
解释: L = 50, V = 5, III = 3.</code></pre><p><strong>示例 5:</strong></p>
<pre><code>输入: num = 1994
输出: &quot;MCMXCIV&quot;
解释: M = 1000, CM = 900, XC = 90, IV = 4.</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= num &lt;= 3999</li>
</ul>
<p><strong>题解：</strong></p>
<p>第一想到贪心，使用哈希表排序罗马数字并遍历，从高到低进行匹配。暴力匹配也可以的，</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    string intToRoman(int num) {
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string ans;
        int 
        for (int i = 0; i < 13; i ++ ) 
            while(num >= values[i])
            {
                num -= values[i];
                ans += reps[i];
            }
        return ans;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day19】13-罗马数字转整数"><a href="#【Day19】13-罗马数字转整数" class="headerlink" title="【Day19】13.罗马数字转整数"></a>【Day19】13.罗马数字转整数</h2><h4 id="13-罗马数字转整数"><a href="#13-罗马数字转整数" class="headerlink" title="13. 罗马数字转整数"></a><a href="https://leetcode-cn.com/problems/roman-to-integer/" target="_blank" rel="noopener">13. 罗马数字转整数</a></h4><p>罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。</p>
<pre><code>字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000</code></pre><blockquote>
<p>例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。</p>
</blockquote>
<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：</p>
<ul>
<li>I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。</li>
<li>X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 </li>
<li>C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。</li>
</ul>
<p>给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。</p>
<p><strong>示例 1:</strong></p>
<pre><code>输入: &quot;III&quot;
输出: 3</code></pre><p><strong>示例 2:</strong></p>
<pre><code>输入: &quot;IV&quot;
输出: 4</code></pre><p><strong>示例 3:</strong></p>
<pre><code>输入: &quot;IX&quot;
输出: 9</code></pre><p><strong>示例 4:</strong></p>
<pre><code>输入: &quot;LVIII&quot;
输出: 58
解释: L = 50, V= 5, III = 3.</code></pre><p><strong>示例 5:</strong></p>
<pre><code>输入: &quot;MCMXCIV&quot;
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= s.length &lt;= 15</li>
<li>s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)</li>
<li>题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内</li>
<li>题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。</li>
<li>IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。</li>
<li>关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。</li>
</ul>
<p><strong>题解：</strong></p>
<ul>
<li><p>当小值在大值的左边，则减小值，如 IV=5-1=4；</p>
</li>
<li><p>当小值在大值的右边，则加小值，如 VI=5+1=6；</p>
</li>
<li><p>小值放在大值的左边，就是做减法，否则为加法。</p>
</li>
</ul>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int romanToInt(string s) {
    int r=0;

    for(int i=0;i<s.length();i++)
    {
        switch(s[i])
        {
            case 'I' : r += ('V' == s[i+1] || 'X' == s[i+1]) ?-1 : 1 ; break;
            case 'V' : r += 5; break;
            case 'X' : r += ('L' == s[i+1] || 'C' == s[i+1]) ?-10: 10 ; break;
            case 'L' : r += 50; break;
            case 'C' : r += ('D' == s[i+1] || 'M' == s[i+1]) ?-100: 100 ; break;
            case 'D' : r += 500; break;
            case 'M' : r += 1000; break;
        }
    }
    return r;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day20】421-数组中两个数的最大异或值"><a href="#【Day20】421-数组中两个数的最大异或值" class="headerlink" title="【Day20】421.数组中两个数的最大异或值"></a>【Day20】421.数组中两个数的最大异或值</h2><h4 id="421-数组中两个数的最大异或值"><a href="#421-数组中两个数的最大异或值" class="headerlink" title="421. 数组中两个数的最大异或值"></a><a href="https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/" target="_blank" rel="noopener">421. 数组中两个数的最大异或值</a></h4><p>给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j &lt; n 。</p>
<p>进阶：你可以在 O(n) 的时间解决这个问题吗？</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [0]
输出：0</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：nums = [2,4]
输出：6</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：nums = [8,10,2]
输出：10</code></pre><p><strong>示例 5：</strong></p>
<pre><code>输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= nums.length &lt;= 2 * 104</li>
<li>0 &lt;= nums[i] &lt;= 231 - 1</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>前缀树</strong></p>
<p>将所有数据从最高位开始取每一个bit，构建出树形结构，尽可能保证最高位为1，也就是说当循环到当前数的时候，如果当前数的bit与当前数中某一个数的某一位是相反的，那么可以保证为1，也就是最大，否则向低位继续循环。</p>
<pre class="line-numbers language-c++"><code class="language-c++">struct Node{
    Node* next[2] = {nullptr};
};
class Solution {
public:
    void insert(int num, Node* root) {
        for (int i = 30; i >= 0; --i) {
            int t = (num >> i & 1);
            if (!root->next[t]) {
                root->next[t] = new Node();
            }
            root = root->next[t];
        }
    }
    int findMaximumXOR(vector<int>& nums) {
        Node* root = new Node();
        for (auto val : nums) {
            insert(val, root);
        }
        int res = 0, tmp = 0;
        Node* p = root;
        for (auto val : nums) {
            p = root; tmp = 0;
            for (int i = 30; i >= 0; --i) {
                int t = (val >> i) & 1;
                if (p->next[!t]) {
                    p = p->next[!t];
                    tmp += (1 << i);
                }else p = p->next[t];
            }
            res = max(res, tmp);
        }
        return res;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>暴力+剪枝</strong></p>
<p>剪枝策略两数异或最大不超过两数之和，先排序再剪枝。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](auto a, auto b) {return a > b;});
        int ans = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                long long x = (long long)nums[i] + nums[j];
                if (ans > x) break;
                ans = max(ans, nums[i] ^ nums[j]);
            }
        }
        return ans;     
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day21】993-二叉树的堂兄弟节点"><a href="#【Day21】993-二叉树的堂兄弟节点" class="headerlink" title="【Day21】993.二叉树的堂兄弟节点"></a>【Day21】993.二叉树的堂兄弟节点</h2><h4 id="993-二叉树的堂兄弟节点"><a href="#993-二叉树的堂兄弟节点" class="headerlink" title="993. 二叉树的堂兄弟节点"></a><a href="https://leetcode-cn.com/problems/cousins-in-binary-tree/" target="_blank" rel="noopener">993. 二叉树的堂兄弟节点</a></h4><p>在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。</p>
<p>如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。</p>
<p>我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。</p>
<p>只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。</p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-01.png" alt></p>
<pre><code>输入：root = [1,2,3,4], x = 4, y = 3
输出：false</code></pre><p><strong>示例 2：</strong></p>
<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-02.png" alt></p>
<pre><code>输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true</code></pre><p><strong>示例 3：</strong></p>
<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/16/q1248-03.png" alt></p>
<pre><code>输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false</code></pre><p><strong>提示：</strong></p>
<ul>
<li>二叉树的节点数介于 2 到 100 之间。</li>
<li>每个节点的值都是唯一的、范围为 1 到 100 的整数。</li>
</ul>
<p><strong>题解：</strong></p>
<p>假设从根节点开始编号1，依次往后编号，其两个孩子是<code>2*n</code>与<code>2*n+1</code>。反过来便是根据两个孩子节点判断是否是同一个父亲，那便是直接除以2，向下取整，看两者是否一样即可。</p>
<p>例如：2、3是同一父亲，2、4不是。</p>
<p>在BFS过程中记录节点编号以及x、y节点，最后判断即可。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> q;
        q.push(root);
        int cnt = 1;
        while (q.size()) {
            int sz = q.size();
            bool xt = false, yt = false;
            int xcnt, ycnt;
            while (sz--) {
                auto p = q.front();
                q.pop();
                if (p) {
                    if (x == p->val) {
                        xt = true;
                        xcnt = cnt;
                    }
                    if (y == p->val) { 
                        yt = true;
                        ycnt = cnt;
                    }

                    if (xt && yt && int(xcnt / 2) != int(ycnt / 2) ) {
                        return true;
                    }
                    q.push(p->left); q.push(p->right);
                }
                cnt++;
            }
        }
        return false;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day22】1442-形成两个异或相等数组的三元组数目"><a href="#【Day22】1442-形成两个异或相等数组的三元组数目" class="headerlink" title="【Day22】1442.形成两个异或相等数组的三元组数目"></a>【Day22】1442.形成两个异或相等数组的三元组数目</h2><h4 id="1442-形成两个异或相等数组的三元组数目"><a href="#1442-形成两个异或相等数组的三元组数目" class="headerlink" title="1442. 形成两个异或相等数组的三元组数目"></a><a href="https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/" target="_blank" rel="noopener">1442. 形成两个异或相等数组的三元组数目</a></h4><p> 给你一个整数数组 arr 。</p>
<p>现需要从数组中取三个下标 i、j 和 k ，其中 (0 &lt;= i &lt; j &lt;= k &lt; arr.length) 。</p>
<p>a 和 b 定义如下：</p>
<ul>
<li>a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]</li>
<li>b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]</li>
</ul>
<p>注意：^ 表示 按位异或 操作。</p>
<p>请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：arr = [1,1,1,1,1]
输出：10</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：arr = [2,3]
输出：0</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：arr = [1,3,5,7,9]
输出：3</code></pre><p><strong>示例 5：</strong></p>
<pre><code>输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= arr.length &lt;= 300</li>
<li>1 &lt;= arr[i] &lt;= 10^8</li>
</ul>
<p><strong>题解：</strong></p>
<p>∵   a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]</p>
<p>​     b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]</p>
<p>∴  arr[i] ^ arr[i + 1] ^ … ^ arr[k] = a ^ b = 0;</p>
<p>a^b=0得到区间[i,k]中有k-i个元组，全部累加即可。区间内三元组的个数为 k - i（因为区间内的任意一个j，都和i，k组成满足题目的一个三元组）。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            int s = arr[i];
            for (int k = i + 1; k < arr.size(); k++) {
                s ^= arr[k];
                if (s == 0) ans += k - i;
            }
        }
        return ans;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day23】1738-找出第-K-大的异或坐标值"><a href="#【Day23】1738-找出第-K-大的异或坐标值" class="headerlink" title="【Day23】1738.找出第 K 大的异或坐标值"></a>【Day23】1738.找出第 K 大的异或坐标值</h2><h4 id="1738-找出第-K-大的异或坐标值"><a href="#1738-找出第-K-大的异或坐标值" class="headerlink" title="1738. 找出第 K 大的异或坐标值"></a><a href="https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/" target="_blank" rel="noopener">1738. 找出第 K 大的异或坐标值</a></h4><p>给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。</p>
<p>矩阵中坐标 (a, b) 的 值 可由对所有满足 0 &lt;= i &lt;= a &lt; m 且 0 &lt;= j &lt;= b &lt; n 的元素 matrix[i][j]（<strong>下标从 0 开始计数</strong>）执行异或运算得到。</p>
<p>请你找出 matrix 的所有坐标中第 k 大的值（<strong>k 的值从 1 开始计数</strong>）。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>m == matrix.length</li>
<li>n == matrix[i].length</li>
<li>1 &lt;= m, n &lt;= 1000</li>
<li>0 &lt;= matrix[i][j] &lt;= 106</li>
<li>1 &lt;= k &lt;= m * n</li>
</ul>
<p><strong>题解：</strong></p>
<p><strong>二维差分+最小堆</strong></p>
<p>前缀和模板+维护k个元素的最小堆</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int prefix[1000][1000];
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix[0][0] = matrix[0][0];
        // 处理第一行
        for (int i = 1; i < n; i++) {
            prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
        }
        // 处理第一列
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
            }
        }

        priority_queue<int, vector<int>, std::greater<int>> pq;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pq.push(prefix[i][j]);
                if (pq.size() > k) pq.pop();
            }
        }
        return pq.top();
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>二分搜值</strong></p>
<p>每次猜测一个值x，然后遍历前缀和矩阵，统计有多少个元素大于等于x，如果count小于k，那么x肯定不可能是答案，我们将猜测的上界下调至x-1；否则，我们就将猜测的下界调整至x。可以看到问题可以转换为查找最后一个小于等于target的数。因为当查找到大于等于target时要往上不断压缩区间，直到小于等于k为止。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int prefix[1000][1000];
    int m, n;
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        m = matrix.size();
        n = matrix[0].size();
        prefix[0][0] = matrix[0][0];
        // 处理第一行
        for (int i = 1; i < n; i++) {
            prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
        }
        // 处理第一列
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
            }
        }

        int left = 0, right = 1e6;
        while (left < right) {
            int mid = right - (right - left - 1) / 2;
            if (count(mid) < k) { // 缩小值
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
    int count (int mid) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (prefix[i][j] >= mid) cnt++;
            }
        }
        return cnt;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day24】692-前K个高频单词"><a href="#【Day24】692-前K个高频单词" class="headerlink" title="【Day24】692.前K个高频单词"></a>【Day24】692.前K个高频单词</h2><h4 id="692-前K个高频单词"><a href="#692-前K个高频单词" class="headerlink" title="692. 前K个高频单词"></a><a href="https://leetcode-cn.com/problems/top-k-frequent-words/" target="_blank" rel="noopener">692. 前K个高频单词</a></h4><p>给一非空的单词列表，返回前 k 个出现次数最多的单词。</p>
<p>返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入: [&quot;i&quot;, &quot;love&quot;, &quot;leetcode&quot;, &quot;i&quot;, &quot;love&quot;, &quot;coding&quot;], k = 2
输出: [&quot;i&quot;, &quot;love&quot;]
解析: &quot;i&quot; 和 &quot;love&quot; 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 &quot;i&quot; 在 &quot;love&quot; 之前。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入: [&quot;the&quot;, &quot;day&quot;, &quot;is&quot;, &quot;sunny&quot;, &quot;the&quot;, &quot;the&quot;, &quot;the&quot;, &quot;sunny&quot;, &quot;is&quot;, &quot;is&quot;], k = 4
输出: [&quot;the&quot;, &quot;is&quot;, &quot;sunny&quot;, &quot;day&quot;]
解析: &quot;the&quot;, &quot;is&quot;, &quot;sunny&quot; 和 &quot;day&quot; 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。</code></pre><p><strong>注意：</strong></p>
<ul>
<li>假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。</li>
<li>输入的单词均由小写字母组成。</li>
</ul>
<p><strong>扩展练习：</strong></p>
<blockquote>
<p>尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。</p>
</blockquote>
<p><strong>题解：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">struct Cmp {
    bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) {
        if(p1.second != p2.second) return p1.second > p2.second;
        else return p1.first < p2.first;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for(string& word : words) m[word]++;
        vector<pair<string, int>> sorted_list(m.begin(), m.end());
        sort(sorted_list.begin(), sorted_list.end(), Cmp());
        vector<string> res;
        for(int i = 0; i < k; i++) res.push_back(sorted_list[i].first);
        return res;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day25】1035-不相交的线"><a href="#【Day25】1035-不相交的线" class="headerlink" title="【Day25】1035.不相交的线"></a>【Day25】1035.不相交的线</h2><h4 id="1035-不相交的线"><a href="#1035-不相交的线" class="headerlink" title="1035. 不相交的线"></a><a href="https://leetcode-cn.com/problems/uncrossed-lines/" target="_blank" rel="noopener">1035. 不相交的线</a></h4><p>在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。</p>
<p>现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：</p>
<ul>
<li>nums1[i] == nums2[j]</li>
<li>且绘制的直线不与任何其他连线（非水平线）相交。</li>
</ul>
<p>请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。</p>
<p>以这种方法绘制线条，并返回可以绘制的最大连线数。</p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/28/142.png" alt></p>
<pre><code>输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= nums1.length &lt;= 500</li>
<li>1 &lt;= nums2.length &lt;= 500</li>
<li>1 &lt;= nums1[i], nums2[i] &lt;= 2000</li>
</ul>
<p><strong>题解：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    vector<vector<int>> dp;
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        dp = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day26】810-黑板异或游戏"><a href="#【Day26】810-黑板异或游戏" class="headerlink" title="【Day26】810.黑板异或游戏"></a>【Day26】810.黑板异或游戏</h2><h4 id="810-黑板异或游戏"><a href="#810-黑板异或游戏" class="headerlink" title="810. 黑板异或游戏"></a><a href="https://leetcode-cn.com/problems/chalkboard-xor-game/" target="_blank" rel="noopener">810. 黑板异或游戏</a></h4><p>黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）</p>
<p>换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。</p>
<p>假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。</p>
<p><strong>示例：</strong></p>
<pre><code>输入: nums = [1, 1, 2]
输出: false
解释: 
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= N &lt;= 1000</li>
<li>0 &lt;= nums[i] &lt;= 2^16</li>
</ul>
<p><strong>题解：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    bool xorGame(vector<int>& nums) {
        //数组元素个数是奇数/偶数，有决定性作用：
        //如果是偶数，先手必胜；
        //如果是奇数，只有当一上来所有元素异或的结果为0，先手才获胜，
        //否则，接下来轮到后手，此时元素个数为偶数，则后手必胜，先手必败！
        int len = nums.size(), t = 0;
        if(len % 2)
        {
            for(auto& x:nums) t ^= x; //所有元素异或的结果
            if(t) return false;
            else return true;
        }
        else return true;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day27】1707-与数组中元素的最大异或值"><a href="#【Day27】1707-与数组中元素的最大异或值" class="headerlink" title="【Day27】1707.与数组中元素的最大异或值"></a>【Day27】1707.与数组中元素的最大异或值</h2><h4 id="1707-与数组中元素的最大异或值"><a href="#1707-与数组中元素的最大异或值" class="headerlink" title="1707. 与数组中元素的最大异或值"></a><a href="https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/" target="_blank" rel="noopener">1707. 与数组中元素的最大异或值</a></h4><p>给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。</p>
<p>第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] &lt;= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。</p>
<p>返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= nums.length, queries.length &lt;= 105</li>
<li>queries[i].length == 2</li>
<li>0 &lt;= nums[j], xi, mi &lt;= 109</li>
</ul>
<p><strong>题解：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">const int N = 1e5 + 50, M = 32 * N;
int son[M][2];
int idx;

void insert(int x){
    int p = 0;
    for(int i = 31; i >= 0; i--){
        int u = (x >> i) & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}
int query(int x){
    int ans = 0, p = 0;
    for(int i = 31; i >= 0; i--){
        int u = (x >> i) & 1;
        if(son[p][!u]) {
            ans += (1 << i);
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return ans;
}

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        memset(son,0,sizeof son);
        idx = 0;
        sort(nums.begin(),nums.end());
        //离线思想，因此需要对queries加一个pos，因为回答是乱序的
        int pos = 0;
        for(auto& q: queries){
            q.push_back(pos++);
        }
        sort(queries.begin(),queries.end(),[](const auto& a,const auto& b){
            return a[1] < b[1];
        });
        vector<int> ans(queries.size());
        int cur = 0;
        for(const auto& q : queries){
            int xi = q[0], mi = q[1],id = q[2];
            while(cur < nums.size() and nums[cur] <= mi){
                insert(nums[cur]);
                cur++;
            }
            if(cur == 0) ans[id] = -1;
            else ans[id] = query(xi);
        }
        return ans;
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day28】664-奇怪的打印机"><a href="#【Day28】664-奇怪的打印机" class="headerlink" title="【Day28】664.奇怪的打印机"></a>【Day28】664.奇怪的打印机</h2><h4 id="664-奇怪的打印机"><a href="#664-奇怪的打印机" class="headerlink" title="664. 奇怪的打印机"></a><a href="https://leetcode-cn.com/problems/strange-printer/" target="_blank" rel="noopener">664. 奇怪的打印机</a></h4><p>有台奇怪的打印机有以下两个特殊要求：</p>
<ul>
<li>打印机每次只能打印由 同一个字符 组成的序列。</li>
<li>每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。</li>
</ul>
<p>给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = &quot;aaabbb&quot;
输出：2
解释：首先打印 &quot;aaa&quot; 然后打印 &quot;bbb&quot;。</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：s = &quot;aba&quot;
输出：2
解释：首先打印 &quot;aaa&quot; 然后在第二个位置打印 &quot;b&quot; 覆盖掉原来的字符 &#39;a&#39;。</code></pre><p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= s.length &lt;= 100</li>
<li>s 由小写英文字母组成</li>
</ul>
<p><strong>题解：</strong></p>
<p>区间dp问题，对于[i,j]区间i&lt;j，如果s[i] == s[j]，那么dp[i][j] = dp[i - 1][j] 或者dp[i + 1][j]，例如：aba 等于 ab或者 ba</p>
<p>如果s[i]!=s[j]，那么对于区间[i,j]的所有组合，进行累加求min即可。</p>
<p>dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])</p>
<p>目标是求dp[0][n - 1]，因此，对于这道题有两种遍历方式。</p>
<p><strong>第一种：从下往上，从左到右。</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int strangePrinter(string s) {
        // aba
        // aaabbb
        int n = s.size();
        int dp[n][n];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    for (int k = i; k < j; k++) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }     
        return dp[0][n - 1];
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>第二种：斜着遍历。</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    int strangePrinter(string s) {
        // aba
        // aaabbb
        int n = s.size();
        int dp[n][n];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int l = 2; l <= n; l++) {
            for (int i = 0; i < n - l + 1; i++) {
                int j = l + i - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    for (int k = i; k < j; k++) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }


        return dp[0][n - 1];
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day29】1787-使所有区间的异或结果为零"><a href="#【Day29】1787-使所有区间的异或结果为零" class="headerlink" title="【Day29】1787.使所有区间的异或结果为零"></a>【Day29】1787.使所有区间的异或结果为零</h2><h4 id="1787-使所有区间的异或结果为零"><a href="#1787-使所有区间的异或结果为零" class="headerlink" title="1787. 使所有区间的异或结果为零"></a><a href="https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/" target="_blank" rel="noopener">1787. 使所有区间的异或结果为零</a></h4><p>给你一个整数数组 nums 和一个整数 k 。区间 [left, right]（left &lt;= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR … XOR nums[right] 。</p>
<p>返回数组中 <strong>要更改的最小元素数</strong> ，以使所有长度为 k 的区间异或结果等于零。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]</code></pre><p><strong>提示：</strong></p>
<ul>
<li><p>1 &lt;= k &lt;= nums.length &lt;= 2000</p>
</li>
<li><p>0 &lt;= nums[i] &lt; 210</p>
<p><strong>题解：</strong></p>
</li>
</ul>
<p>第一种情况采用贪心的方法求得最优解。因为修改后的元素可能是原序列中没有出现过的元素。如果修改的某一列的元素是原序列中没有出现过的元素，那么这种情况下一定可以用贪心的办法求出最优解，做法是将众数最小的一列中的每个数变成一个全新的，该列中没有出现的，使得每个周期内的元素的异或和为0的数。</p>
<p>第二种情况采用dp的方法求得最优解在这种情况下，由于没有最终修改后的元素是原数组中存在的数，因此可以从前往后枚举每一列，然后枚举选择第几行的数作为这列元素修改后的元素，由于异或具有交换性质，因此不具有顺序的问题，所以可以采用dp的方法递推出将序列变成数组中本来存在的某个数的情况。边界，f[0] [0] = 0，目标状态是f[k] [0]，状态表示f[i] [j]为前i列异或和为j的情况下的最小值。</p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    // 1.某一列用了一个全新的数
    // 2.每一列用了原来的数

    const int N = 1024, INF = 1e8;
    int s[1024]; // 求众数
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size(), m = (n + k - 1) / k;
        vector<vector<int>> f(k + 1, vector<int>(N, INF));
        int cnt = 0, minv = INF; // 每一列代价
        // f[i][j] 第i列的异或和为j
        f[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            int len = m;
            memset(s, 0 , sizeof s);
            if (n % k && n % k < i) len--;
            for (int j = 0; j < len; j ++) {
                s[nums[j * k + i - 1]]++;
            }
            int maxv = 0;
            for (int j = 0; j < N; j++) {
                maxv = max(maxv, s[j]);
            }
            cnt += len - maxv;
            minv = min(minv, maxv); // 众数最少的那一列  不用众数  而用全新的数

            for (int j = 0; j < N; j++) { // 异或和为j
                for (int u = 0; u < len; u++) { // 每一行
                    int x = nums[u * k + i - 1], cost = len - s[x];
                    f[i][j] = min(f[i][j], f[i - 1][j ^ x] + cost);
                }
            }
        }
        // cnt: 每一列的代价
        // minv表示 某一列不用众数时的代价 si - maxv -> si 变成全新的数代价
        return min(cnt + minv, f[k][0]);
    }
};<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="【Day30】1190-反转每对括号间的子串"><a href="#【Day30】1190-反转每对括号间的子串" class="headerlink" title="【Day30】1190.反转每对括号间的子串"></a>【Day30】1190.反转每对括号间的子串</h2><h4 id="1190-反转每对括号间的子串"><a href="#1190-反转每对括号间的子串" class="headerlink" title="1190. 反转每对括号间的子串"></a><a href="https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/" target="_blank" rel="noopener">1190. 反转每对括号间的子串</a></h4><p>给出一个字符串 s（仅含有小写英文字母和括号）。</p>
<p>请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。</p>
<p><strong>注意，您的结果中 不应 包含任何括号。</strong></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = &quot;(abcd)&quot;
输出：&quot;dcba&quot;</code></pre><p><strong>示例 2：</strong></p>
<pre><code>输入：s = &quot;(u(love)i)&quot;
输出：&quot;iloveu&quot;</code></pre><p><strong>示例 3：</strong></p>
<pre><code>输入：s = &quot;(ed(et(oc))el)&quot;
输出：&quot;leetcode&quot;</code></pre><p><strong>示例 4：</strong></p>
<pre><code>输入：s = &quot;a(bcdefghijkl(mno)p)q&quot;
输出：&quot;apmnolkjihgfedcbq&quot;</code></pre><p><strong>提示：</strong></p>
<ul>
<li>0 &lt;= s.length &lt;= 2000</li>
<li>s 中只有小写英文字母和括号</li>
<li>我们确保所有括号都是成对出现的</li>
</ul>
<p><strong>题解：</strong></p>
<p><img src="https://cdn.acwing.com/media/article/image/2021/05/26/30502_ed3e6737bd-aa.gif" alt></p>
<p>挨个遍历， 左括号和普通字符直接入栈；遇到右括号 ，就依次出栈直到栈顶为左括号 ，出栈的这些字符按出栈顺序链接自然也就是逆序的，然后栈顶左括号出栈 把组合成的逆序串重新压入栈。</p>
<p>遍历完字符串 栈中从栈底到栈顶 自然也就想要的结果，如果依次出栈 要注意连接顺序，还需要一次整体反转。</p>
<p><strong>代码：</strong></p>
<pre class="line-numbers language-c++"><code class="language-c++">class Solution {
public:
    string reverseParentheses(string s) {
        stack<char> st;
        for (auto c : s) {
            if (c != ')') {
                st.push(c);
            } else {
                string tmp;
                while (st.top() != '(') {
                    tmp += st.top();
                    st.pop();
                }
                st.pop();
                for (auto s : tmp) {
                    st.push(s);
                }
            }
        }
        string ans;
        while (!st.empty()) {
            ans = st.top() + ans; st.pop();
        }
        return ans;
    }
};
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p>几天刚好一个月结束啦，收获还是很多的，困难我唯唯诺诺，简单重拳出击！！！hhh~</p>

            </div>
            <hr />

            
            <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.88rem;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-large waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fa fa-close"></i></a>
            <h4 class="reward-title">写作不易，客官能否打赏一杯奶茶？</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/reward/alipay.jpg" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>
            

            <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">

<div id="article-share">
    
    <div class="social-share" data-disabled="qzone" data-wechat-qrcode-helper="<p>微信里点“发现”->“扫一扫”二维码便可查看分享。</p>"></div>
    
</div>

<script src="/libs/share/js/social-share.min.js"></script>

            

    <div class="reprint" id="reprint-statement">
        <p class="reprint-tip">
            <i class="fa fa-exclamation-triangle"></i>&nbsp;&nbsp;
            <span>转载规则</span>
        </p>
        
            <div class="center-align">
                <a rel="license" href="https://creativecommons.org/licenses/by/4.0/deed.zh">
                    <img alt=""
                         style="border-width:0"
                         src="https://i.creativecommons.org/l/by/4.0/88x31.png"/>
                </a>
            </div>
            <br/>
            <span xmlns:dct="http://purl.org/dc/terms/" href="http://purl.org/dc/dcmitype/Text"
                  property="dct:title" rel="dct:type">
                    《暑假LeetCode刷题集合（上）》
                </span> 由
            <a xmlns:cc="http://creativecommons.org/ns#" href="/shu-jia-leetcode-shua-ti-ji-he-shang.html" property="cc:attributionName"
               rel="cc:attributionURL">
                Tyzhao
            </a> 采用
            <a rel="license" href="https://creativecommons.org/licenses/by/4.0/deed.zh">
                知识共享署名 4.0 国际许可协议
            </a>进行许可。
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>


        </div>
    </div>

    
    <link rel="stylesheet" href="/libs/gitalk/gitalk.css">
<link rel="stylesheet" href="/css/my-gitalk.css">

<div class="card gitalk-card" data-aos="fade-up">
    <div id="gitalk-container" class="card-content"></div>
</div>

<script src="/libs/gitalk/gitalk.min.js"></script>
<script>
    let gitalk = new Gitalk({
        clientID: '46697bb9a799731534b2',
        clientSecret: 'b4f73ab06fb0a67da32d620ebc395111f2d508ee',
        repo: 'muyiio.github.io',
        owner: 'MUYIio',
        admin: "MUYIio",
        id: 'shu-jia-leetcode-shua-ti-ji-he-shang.html',
        distractionFreeMode: false  // Facebook-like distraction free mode
    });

    gitalk.render('gitalk-container');
</script>
    

    

    

    

    
    <style>
    .valine-card {
        margin: 1.5rem auto;
    }

    .valine-card .card-content {
        padding: 20px 20px 5px 20px;
    }

    #vcomments input[type=text],
    #vcomments input[type=email],
    #vcomments input[type=url],
    #vcomments textarea {
        box-sizing: border-box;
    }

    #vcomments p {
        margin: 2px 2px 10px;
        font-size: 1.05rem;
        line-height: 1.78rem;
    }

    #vcomments blockquote p {
        text-indent: 0.2rem;
    }

    #vcomments a {
        padding: 0 2px;
        color: #42b983;
        font-weight: 500;
        text-decoration: underline;
    }

    #vcomments img {
        max-width: 100%;
        height: auto;
        cursor: pointer;
    }

    #vcomments ol li {
        list-style-type: decimal;
    }

    #vcomments ol,
    ul {
        display: block;
        padding-left: 2em;
        word-spacing: 0.05rem;
    }

    #vcomments ul li,
    ol li {
        display: list-item;
        line-height: 1.8rem;
        font-size: 1rem;
    }

    #vcomments ul li {
        list-style-type: disc;
    }

    #vcomments ul ul li {
        list-style-type: circle;
    }

    #vcomments table, th, td {
        padding: 12px 13px;
        border: 1px solid #dfe2e5;
    }

    #vcomments table, th, td {
        border: 0;
    }

    table tr:nth-child(2n), thead {
        background-color: #fafafa;
    }

    #vcomments table th {
        background-color: #f2f2f2;
        min-width: 80px;
    }

    #vcomments table td {
        min-width: 80px;
    }

    #vcomments h1 {
        font-size: 1.85rem;
        font-weight: bold;
        line-height: 2.2rem;
    }

    #vcomments h2 {
        font-size: 1.65rem;
        font-weight: bold;
        line-height: 1.9rem;
    }

    #vcomments h3 {
        font-size: 1.45rem;
        font-weight: bold;
        line-height: 1.7rem;
    }

    #vcomments h4 {
        font-size: 1.25rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    #vcomments h5 {
        font-size: 1.1rem;
        font-weight: bold;
        line-height: 1.4rem;
    }

    #vcomments h6 {
        font-size: 1rem;
        line-height: 1.3rem;
    }

    #vcomments p {
        font-size: 1rem;
        line-height: 1.5rem;
    }

    #vcomments hr {
        margin: 12px 0;
        border: 0;
        border-top: 1px solid #ccc;
    }

    #vcomments blockquote {
        margin: 15px 0;
        border-left: 5px solid #42b983;
        padding: 1rem 0.8rem 0.3rem 0.8rem;
        color: #666;
        background-color: rgba(66, 185, 131, .1);
    }

    #vcomments pre {
        font-family: monospace, monospace;
        padding: 1.2em;
        margin: .5em 0;
        background: #272822;
        overflow: auto;
        border-radius: 0.3em;
        tab-size: 4;
    }

    #vcomments code {
        font-family: monospace, monospace;
        padding: 1px 3px;
        font-size: 0.92rem;
        color: #e96900;
        background-color: #f8f8f8;
        border-radius: 2px;
    }

    #vcomments pre code {
        font-family: monospace, monospace;
        padding: 0;
        color: #e8eaf6;
        background-color: #272822;
    }

    #vcomments pre[class*="language-"] {
        padding: 1.2em;
        margin: .5em 0;
    }

    #vcomments code[class*="language-"],
    pre[class*="language-"] {
        color: #e8eaf6;
    }

    #vcomments [type="checkbox"]:not(:checked), [type="checkbox"]:checked {
        position: inherit;
        margin-left: -1.3rem;
        margin-right: 0.4rem;
        margin-top: -1px;
        vertical-align: middle;
        left: unset;
        visibility: visible;
    }

    #vcomments b,
    strong {
        font-weight: bold;
    }

    #vcomments dfn {
        font-style: italic;
    }

    #vcomments small {
        font-size: 85%;
    }

    #vcomments cite {
        font-style: normal;
    }

    #vcomments mark {
        background-color: #fcf8e3;
        padding: .2em;
    }

    #vcomments table, th, td {
        padding: 12px 13px;
        border: 1px solid #dfe2e5;
    }

    table tr:nth-child(2n), thead {
        background-color: #fafafa;
    }

    #vcomments table th {
        background-color: #f2f2f2;
        min-width: 80px;
    }

    #vcomments table td {
        min-width: 80px;
    }

    #vcomments [type="checkbox"]:not(:checked), [type="checkbox"]:checked {
        position: inherit;
        margin-left: -1.3rem;
        margin-right: 0.4rem;
        margin-top: -1px;
        vertical-align: middle;
        left: unset;
        visibility: visible;
    }
</style>

<div class="card valine-card" data-aos="fade-up">
    <div id="vcomments" class="card-content"></div>
</div>

<script src="/libs/valine/av-min.js"></script>
<script src="/libs/valine/Valine.min.js"></script>
<!-- <script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script> -->

<script>
    new Valine({
        el: '#vcomments',
        appId: '2XytdtE76cEw5tyzKupUSM2s-gzGzoHsz',
        appKey: 'CFpPusBW6xLPhs8OQUaCkX2c',
        notify: 'true' === 'true',
        verify: 'false' === 'true',
        visitor: 'false' === 'true',
        avatar: 'wavatar',
        pageSize: '10',
        lang: 'zh-cn',
        placeholder: '如果你没有GitHub账号，还可以在这里评论啦！'
    });
</script>

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fa fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/shi-yong-java-kai-fa-yi-ge-ji-shi-ben.html">
                    <div class="card-image">
                        
                        
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/7.jpg" class="responsive-img" alt="使用Java开发一个记事本">
                        
                        <span class="card-title">使用Java开发一个记事本</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            大二下的Java课程设计，仿的Windows记事本，使用Java Swing组件开发。
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="fa fa-clock-o fa-fw icon-date"></i>2021-07-17
                        </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Java/" class="post-category" target="_blank">
                                    Java
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Demo/" target="_blank">
                        <span class="chip bg-color">Demo</span>
                    </a>
                    
                    <a href="/tags/Notepad/" target="_blank">
                        <span class="chip bg-color">Notepad</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fa fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/x86-hui-bian-yu-yan-cong-shi-mo-shi-dao-bao-hu-mo-shi-yue-du-bi-ji.html">
                    <div class="card-image">
                        
                        
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/34.jpg" class="responsive-img" alt="《X86汇编语言从实模式到保护模式》阅读笔记">
                        
                        <span class="card-title">《X86汇编语言从实模式到保护模式》阅读笔记</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            能够了解常见的汇编命令，实现能够看懂基本的汇编操作，理解所表示含义。
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="fa fa-clock-o fa-fw icon-date"></i>2021-05-16
                            </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/操作系统/" class="post-category" target="_blank">
                                    操作系统
                                </a>
                            
                            <a href="/categories/操作系统/汇编/" class="post-category" target="_blank">
                                    汇编
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/学习笔记/" target="_blank">
                        <span class="chip bg-color">学习笔记</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>
</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: Shawlon`s Blog<br />'
            + '作者: Tyzhao<br />'
            + '链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () { bodyElement.removeChild(newdiv); }, 200);
    });
</script>

    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget">
            <div class="toc-title"><i class="fa fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fa fa-list"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            // headingsOffset: -205,
            headingSelector: 'h1, h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).slideUp(500);
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).slideDown(500);
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>
    

</main>


<script src="https://cdn.bootcss.com/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
    MathJax.Hub.Config({
        tex2jax: {inlineMath: [['$', '$'], ['\(', '\)']]}
    });
</script>

<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>
<!-- 代码语言 -->
<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>
<!-- 代码块复制 -->
<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>
<script type="text/javascript" src="/libs/codeBlock/clipboard.min.js"></script>
<!-- 代码块收缩 -->
<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script> 
<!-- 代码块折行 -->
<style type="text/css">code[class*="language-"], pre[class*="language-"] { white-space: pre !important; }</style>


    <footer class="page-footer bg-color">
    <div class="container row center-align">
       <div class="Copy-right">
            &copy; 2021 Yshawlon. All Rights Reserved.

           <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/icp.png" style="width:18px;height:18px;margin-bottom:-2px" alt="ICP">
           <a href="https://beian.miit.gov.cn/#/Integrated/index" target="_blank">渝ICP备2020014220号-1</a>丨
           <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/moeicp.png" style="width:18px;height:18px;margin-bottom:-3px" alt="MOE ICP">
           <a href="https://icp.gov.moe/" target="_blank">萌ICP备20216999号</a>丨            
           <!--<a href="/sitemap.xml" target="_blank">站点地图</a>丨-->
           
            &nbsp;<i class="fa fa-area-chart"></i>&nbsp;站点总字数:&nbsp;
            <span class="white-color">72.3k
             丨            
            <a href="https://tongji.baidu.com/web/welcome/ico?s=df42dpc7224a5f6a8d435" target="_blank">百度统计</a>丨
           <script type="text/javascript">document.write(unescape("%3Cspan id='cnzz_stat_icon_1278720284'%3E%3C/span%3E%3Cscript src='https://s9.cnzz.com/z_stat.php%3Fid%3D1278720284%26show%3Dpic' type='text/javascript'%3E%3C/script%3E"));</script>

            <span id="sitetime"></span>

            
            
            
            
            <span id="busuanzi_container_site_pv" style='display:none'>
                <i class="fa fa-users"></i>
                本站总访问量 <span id="busuanzi_value_site_pv" class="red-color"></span>
            </span>
            
            
            <span id="busuanzi_container_site_uv" style='display:none'>
               人次,&nbsp;<i class="fa fa-user"></i>访客数 <span id="busuanzi_value_site_uv" class="blue-color"></span> 人.
            </span>
            
            
        </div>        
        <div class="social-link social-statis">
    <a href="https://github.com/MUYIio" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fa fa-github"></i>
    </a>



    <a href="https://www.csdn.net/weixin_45682081" class="tooltipped" target="_blank" data-tooltip="访问我的CSDN主页" data-position="top" data-delay="50">
        <i class="fa fa-codiepie"></i>
    </a>



    <a href="https://www.zhihu.com/zhihu.com/people/muyiio" class="tooltipped" target="_blank" data-tooltip="访问我的知乎" data-position="top" data-delay="50">
        <i class="fa fa-inverse">知</i>
    </a>



    <a href="https://user.qzone.qq.com/1571504536" class="tooltipped" target="_blank" data-tooltip="访问我的QQ空间" data-position="top" data-delay="50">
        <i class="fa fa-qq"></i>
    </a>



    <a href="mailto:1571504536@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fa fa-envelope-open"></i>
    </a>



    <a href="/atom.xml" class="tooltipped" target="_blank" data-tooltip="RSS 订阅" data-position="top" data-delay="50">
        <i class="fa fa-rss"></i>
    </a>
</div>


    </div>
    <div class="container row center-align">
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://hexo.io/" target="_blank" title="由 Hexo 强力驱动">
      <span class="badge-subject">Powered</span><span class="badge-value bg-blue">Hexo</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://github.com/" target="_blank" title="静态网页托管于 GitHub Pages 和 Coding Pages">
      <span class="badge-subject">Hosted</span><span class="badge-value bg-brightgreen">GitHub & Coding</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://www.cloud.tencent.com/" target="_blank" title="腾讯云提供域名相关服务">
      <span class="badge-subject">DNS</span><span class="badge-value bg-blueviolet">Tencent cloud</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://www.jsdelivr.com/" target="_blank" title="jsDelivr 提供 CDN 加速服务">
      <span class="badge-subject">CDN</span><span class="badge-value bg-orange">jsDelivr</span></a>
    </div>
    <div class="github-badge">
        <a style="color: #fff" rel="license" href="https://github.com/blinkfox/hexo-theme-matery/" target="_blank" title="站点使用 Matery 主题">
      <span class="badge-subject">Theme</span><span class="badge-value bg-blue">Matery</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="本站点采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可">
      <span class="badge-subject"><i class="fa fa-copyright"></i></span><span class="badge-value bg-lightgrey">BY-NC-SA 4.0</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://996.icu/" target="_blank" title="支持 996.ICU">
      <span class="badge-subject">Link</span><span class="badge-value bg-red">996.ICU</span></a>
    </div>
    <div class="github-badge">
      <span class="badge-subject">WordCount</span><span class="badge-value bg-blueviolet">72.3k</span>
    </div>
</footer>

<div class="progress-bar"></div>

<!-- 不蒜子计数初始值纠正 -->
<script>
    $(document).ready(function () {

        var int = setInterval(fixCount, 50);
        var pvcountOffset = 80000;
        var uvcountOffset = 20000;

        function fixCount() {
            if (document.getElementById("busuanzi_container_site_pv").style.display != "none") {
                $("#busuanzi_value_site_pv").html(parseInt($("#busuanzi_value_site_pv").html()) + pvcountOffset);
                clearInterval(int);
            }
            if ($("#busuanzi_container_site_pv").css("display") != "none") {
                $("#busuanzi_value_site_uv").html(parseInt($("#busuanzi_value_site_uv").html()) + uvcountOffset); // 加上初始数据 
                clearInterval(int);
            }
        }
    });
</script>

<script language=javascript>
    function siteTime() {
        window.setTimeout("siteTime()", 1000);
        var seconds = 1000;
        var minutes = seconds * 60;
        var hours = minutes * 60;
        var days = hours * 24;
        var years = days * 365;
        var today = new Date();
        var todayYear = today.getFullYear();
        var todayMonth = today.getMonth() + 1;
        var todayDate = today.getDate();
        var todayHour = today.getHours();
        var todayMinute = today.getMinutes();
        var todaySecond = today.getSeconds();
        /* Date.UTC() -- 返回date对象距世界标准时间(UTC)1970年1月1日午夜之间的毫秒数(时间戳)
        year - 作为date对象的年份，为4位年份值
        month - 0-11之间的整数，做为date对象的月份
        day - 1-31之间的整数，做为date对象的天数
        hours - 0(午夜24点)-23之间的整数，做为date对象的小时数
        minutes - 0-59之间的整数，做为date对象的分钟数
        seconds - 0-59之间的整数，做为date对象的秒数
        microseconds - 0-999之间的整数，做为date对象的毫秒数 */
        var t1 = Date.UTC(2020, 01, 01, 00, 00, 00); //北京时间2018-2-13 00:00:00
        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
        var diff = t2 - t1;
        var diffYears = Math.floor(diff / years);
        var diffDays = Math.floor((diff / days) - diffYears * 365);
        var diffHours = Math.floor((diff - (diffYears * 365 + diffDays) * days) / hours);
        var diffMinutes = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours) / minutes);
        var diffSeconds = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours - diffMinutes * minutes) / seconds);
        document.getElementById("sitetime").innerHTML = " | 本站已运行 " + diffYears + " 年 " + diffDays + " 天 " + diffHours + " 小时 " + diffMinutes + " 分钟 " + diffSeconds + " 秒";
    }/*因为建站时间还没有一年，就将之注释掉了。需要的可以取消*/
    siteTime();
</script>

    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fa fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script src="/js/search.js"></script>
<script type="text/javascript">
$(function () {
    searchFunc("/" + "search.xml", 'searchInput', 'searchResult');
});
</script>
    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fa fa-angle-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    <script type="text/javascript"> var OriginTitile = document.title, st; document.addEventListener("visibilitychange", function () { document.hidden ? (document.title = "Σ(っ °Д °;)っ喔哟，崩溃啦！", clearTimeout(st)) : (document.title = "φ(゜▽゜*)♪咦，又好了！", st = setTimeout(function () { document.title = OriginTitile }, 3e3)) })
    </script>

    <!-- Global site tag (gtag.js) - Google Analytics -->

<script async src="https://www.googletagmanager.com/gtag/js?id="></script>
<script>
    window.dataLayer = window.dataLayer || [];
    function gtag() {
        dataLayer.push(arguments);
    }

    gtag('js', new Date());
    gtag('config', '');
</script>



    <!--鼠标点击特效-->
    


    <!--不蒜子计数-->
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    


    <!-- 雪花特效 -->
    
    
    <!--动态线条背景-->
    <script type="text/javascript"
    color="220,220,220" opacity='0.7' zIndex="-2" count="200" src="//cdn.bootcss.com/canvas-nest.js/1.0.0/canvas-nest.min.js">
    </script>

    <!--鼠标跟随樱花特效 -->
    
        <script type="text/javascript" src="/js/fairyDustCursor.js"></script>
    



    <!--单击显示文字-->
    

    <!--鼠标点击粒子特效-->
    
    <canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
    <script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
    <script type="text/javascript" src="/js/fireworks.js"></script>
    

    <script async src =“ https://www.jsdelivr.com/terms/acceptable-use-policy-jsdelivr-net ”>
    </script>


    <!--自定义看板娘-->
    <!-- <script src="https://cdn.jsdelivr.net/npm/jquery/dist/jquery.min.js"></script>  -->
    <script src="/live2d-widget/autoload.js"></script>
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css"/>


</body>
</html>